package cn.willbj.brief.hootl.sort.demo;

import java.util.Arrays;

public class Demo03 {
	public static void main(String[] args) {
		// int[] arr = {3,5,2,1,9,2,7};
		int[] arr = {3,7,2,1,9,5,8};
		int[] qSort = qSort(arr);
		System.out.println(Arrays.toString(qSort));
	}
	public static int[] qSort(int[] arr)  {
		int[] copyOf = Arrays.copyOf(arr, arr.length);
		qSortBiz(copyOf, 0, copyOf.length-1);
		return copyOf;
	}
	
	public static void qSortBiz(int[] copyOf,int left,int right) {
		if (left >= right) {
			return;
		}
		int param = param(copyOf, left, right);
		qSortBiz(copyOf, left, param-1);
		qSortBiz(copyOf, param+1, right);
	}
	
	public static int param(int[] copyOf,int left,int right) {
		int param = left;
		int index = param+1;
		
		for (int i = index; i <= right; i++) {
			if (copyOf[param] > copyOf[i]) {
				swap(copyOf, index, i);
				index ++;
			}
		}
		
		swap(copyOf, index-1, param);
		return index-1;
	}
	
	public static void swap(int[] copyOf,int index,int i) {
		if (index == i) {
			return;
		}
		int temp = copyOf[index];
		copyOf[index] = copyOf[i];
		copyOf[i] = temp;
	}
	
	
}
